# 63/100 二分查找-搜索插入位置
# leetcode第35题: https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked

from leetcode import test


def searchInsert(nums: list[int], target: int) -> int:
    n = len(nums)
    if n < 2:
        return 0 if nums[0] >= target else 1

    if target < nums[0]:
        return 0
    if target > nums[n - 1]:
        return n

    l, r = 0, n - 1
    while l <= r:
        m = (r + l) // 2
        if target < nums[m]:
            r = m - 1
        elif target > nums[m]:
            l = m + 1
        else:
            return m

    return r + 1


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "target": 2},
           {"nums": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "target": 4},
           {"nums": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "target": 7},
           {"nums": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "target": 0},
           {"nums": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "target": 8},
           {"nums": [1, 4, 6, 7, 8, 9], "target": 6},
           {"nums": [1, 3, 5, 6], "target": 5}, {"nums": [1, 3, 5, 6], "target": 2},
           {"nums": [1, 3, 5, 6], "target": 7}, ]
    out = [1, 3, 6, 0, 7, 2, 2, 1, 4]
    test.test_function(searchInsert, inp, out)
